package com.study.lu.动态规划;

public class 买卖股票的最佳时机II {
    /**
     * 给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。
     * <p>
     * 在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
     * 返回 你能获得的 最大 利润 。
     * <p>
     *  
     * <p>
     * 示例 1:
     * <p>
     * 输入: prices = [7,1,5,3,6,4]
     * 输出: 7
     * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     *      随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
     * 示例 2:
     * <p>
     * 输入: prices = [1,2,3,4,5]
     * 输出: 4
     * 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     *      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
     * 示例 3:
     * <p>
     * 输入: prices = [7,6,4,3,1]
     * 输出: 0
     * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] prices = new int[]{7, 1, 5, 3, 6, 4};
        // 动态规划
        System.out.println(maxProfit(prices));
        // 贪心算法
        System.out.println(maxProfit2(prices));

    }

    /**
     * 贪心算法解法
     * 只要当天比前一天贵，就卖出
     * eg  1 3 7 9 是可以这样求出最优解的
     *
     * @param prices
     * @return
     */
    private static int maxProfit2(int[] prices) {
        int sumPrice = 0;
        for (int i = 1; i < prices.length; i++) {
            int b = prices[i] - prices[i - 1];
            if (b > 0) {
                sumPrice += b;
            }
        }

        return sumPrice;
    }

    /**
     * 动态规划解法
     * <p>
     * 1.定义状态： d[i]][j]
     * i:表示第i天
     * j:有两个值 0：持有现金 1：持有股票数
     * 2.公式：
     * 1.状态从持有现金开始，到最后一天也是关系持有现金数.
     * 2.每天的状态可以是持有现金（卖股票赚钱了）,持有股票（低价买入）。[7,1,5,3,6,4]
     * 3.d[i][0]= max(d[i-1][0],d[i-1][1]+prices[i]);   持有现金数 = max(前一天的持有现金最大值,前一天的持有股票数+第i天卖出的股票价格)。
     * 4.d[i][1]= max(d[i-1][1],d[i-1][0]-prices[i]);   持有股票数 = max(前一天的持有股票最大值,前一天的持有现金数-第i天购买的股票数)。
     * eg：[7,1,5,3,6,4].
     * 第0天：持有现金数 = 0; 持有股票数 =0-7= -7;（如果后续的股票价格大于7块，那么肯定是需要买入的）
     * 第1天：持有现金数 = max(0,-7+1)=0;持有股票数 =max(-7,0-1)=-1;(如果后续的股票价格大于1块，那么肯定是需要买入的,这里是买入1股的花费)
     * 第2天：持有现金数 = max(0,-1+5)=4;持有股票数 =max(-1,0-5)=-1;（买入是）
     * 第3天：持有现金数 = max(1,-1+3)=1;持有股票数 =max(-1,4-3)=1;
     * 第4天：持有现金数 = max(1,1+6)=7;持有股票数 =max(1,1-6)=1;
     * 第5天：持有现金数 = max(7,1+4)=7;持有股票数 =max(1,1-6)=1;
     *
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {

        int[][] dp = new int[prices.length][2];
        // 第一天是没赚钱的 所以是0
        dp[0][0] = 0;
        // 第一天能不能买入是看后面卖出价格是不是比买入的价格高
        dp[0][1] = 0 - prices[0];

        for (int i = 1; i < prices.length; i++) {
            // 第i天的现金数 = max( 第i-1天的现金数，第i-1天的股票数在第i天卖出的金额)
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 第i天的股票数 = max( 第i-1天的股票数，第i-1天的现金数在第i天买入股票价格)
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }


        return dp[prices.length - 1][0];

    }
}
